package leetcode;

public class LongestIncreasingPathInMatrix {

	public static void main(String[] args) {
		LongestIncreasingPathInMatrix object = new LongestIncreasingPathInMatrix();
		int[][] matrix = {{3, 4, 5}, {3, 2, 6}, {2, 1, 1}};
		System.out.println(object.longestIncreasingPath(matrix));
		
	}
	
	//上下左右四个方向
	private final int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}};
	
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length <= 0){
        	return 0;
        }
        
        int[][] memoization = new int[matrix.length][matrix[0].length];
        int maxLength = 0;
    	for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				int curLength = dfs(matrix, memoization, i, j);
				maxLength = Math.max(curLength, maxLength);
				
//				for (int k = 0; k < memoization.length; k++) {
//					for (int k2 = 0; k2 < memoization[0].length; k2++) {
//						System.out.print(memoization[k][k2] + " ");
//					}
//					System.out.println();
//				}
//				System.out.println("-----");
			}
		}
    	return maxLength;
    }
    
    public int dfs(int[][] matrix, int[][] memoization, int x, int y){
    	if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length){
    		return 0;
    	}
    	if(memoization[x][y] != 0){
    		return memoization[x][y];
    	}
    	int ans = 1;
    	for (int i = 0; i < dir.length; i++) {
			int nextX = x + dir[i][0];
			int nextY = y + dir[i][1];
			if(nextX < 0 || nextX >= matrix.length || nextY < 0 || nextY >= matrix[0].length){
	    		continue;
	    	}
			int cur = 0;
			if(matrix[nextX][nextY] > matrix[x][y]){
				cur = dfs(matrix, memoization, nextX, nextY);
				memoization[nextX][nextY] = cur;
				ans = Math.max(ans, cur + 1);
			}
		}
    	return ans;
    }
}
